package com.cat.DataStructure04;

import java.util.Arrays;

/**
 * @author 曲大人的喵
 * @description https://leetcode.cn/problems/longest-common-suffix-queries/
 * @create 2025/11/26 19:33
 * @since JDK17
 */

public class Solution20 {
    static int N = ((int) 5e5) + 10, cnt = 1;
    static int[][] tree = new int[N][26];
    static int[] pass = new int[N];
    static void clear() {
        for (int i = 1; i <= cnt; i++) {
            Arrays.fill(tree[i], 0);
        }
    }
    static void insert(String word, int idx) {
        int cur = 1;
        for (int i = word.length() - 1, path; i >= 0; i--) {    // 将后缀加入字典树 
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                tree[cur][path] = ++cnt;
            }
            cur = tree[cur][path];
            pass[cur] = idx;
        }
    }
    static int search(String word, int idx) {
        int cur = 1;
        for (int i = word.length() - 1, path; i >= 0; i--) {
            path = word.charAt(i) - 'a';
            if (tree[cur][path] == 0) {
                break;
            }
            cur = tree[cur][path];
        }
        return cur != 1 ? pass[cur] : idx;
    }

    public int[] stringIndices(String[] wordsContainer, String[] wordsQuery) {
        int n = wordsContainer.length, m = wordsQuery.length;
        Integer[] arr = new Integer[n];
        int[] ans = new int[m];
        for (int i = 0; i < n; i++) {
            arr[i] = i;
        }
        // 排序
        Arrays.sort(arr, (a, b) -> {
            if (wordsContainer[a].length() != wordsContainer[b].length()) {
                return wordsContainer[a].length() - wordsContainer[b].length();
            } else {
                return a - b;
            }
        });
        cnt = 1;
        for (int i = n - 1; i >= 0; i--) {
            insert(wordsContainer[arr[i]], arr[i]);
        }
        for (int i = 0; i < m; i++) {
            ans[i] = search(wordsQuery[i], arr[0]);
        }

        clear();
        return ans;
    }
}